package personal_exercise;

import javafx.util.Pair;

import java.util.*;
import java.util.stream.Collectors;

public class Demo6 {

    // kanan和高音
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = in.nextInt();

        int res = 0;
        int left = 0, right = 1;
        while (right < n) {
            while (right < n && arr[right] - arr[right - 1] <= 8) right++;
            res = Math.max(res, right - left);
            left = right++;
        }
        System.out.println(res);
    }



    // MT3 拜访
    public int countPath (int[][] CityMap, int n, int m) {
        boolean[][] vis = new boolean[n][m];
        int[] dx = {0,0,1,-1};
        int[] dy = {1,-1,0,0};

        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            boolean flag = false;
            for (int j = 0; j < m; j++) {
                if (CityMap[i][j] == 1) {
                    q.offer(new int[]{i, j});
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }

        int res = 0;
        while (!q.isEmpty()) {
            // 此次 BFS 是否找到顾客
            boolean flag = false;
            for (int sz = q.size(); sz-- > 0; ) {
                int[] arr = q.poll();
                int i = arr[0], j = arr[1];
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < n && y >= 0 && y < m && CityMap[x][y] != -1 && !vis[x][y]) {
                        if (CityMap[x][y] == 2) {
                            flag = true;
                            res++;
                            break;
                        } else {
                            q.offer(new int[]{x, y});
                        }
                    }
                }
            }
            if (flag) break;
        }
        return res;
    }




    // DP33 买卖股票的最好时机(四)
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        int[] prices = new int[n];
        for (int i = 0; i < n; i++) {
            prices[i] = in.nextInt();
        }

        // f[i][j]:第 i 天结束后持有股票,交易次数为 j 的最大收益
        // g[i][j]:第 i 天结束后未持有股票,交易次数为 j 的最大收益
        int[][] f = new int[n][k + 1], g = new int[n][k + 1];
        f[0][0] = -prices[0];
        for (int j = 1; j <= k; j++) f[0][j] = g[0][j] = -0X3f3f3f3f;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j > 0) {
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }

        int res = 0;
        for (int j = 0; j <= k; j++) res = Math.max(res, g[n - 1][j]);
        System.out.println(res);
    }




    //  AOE还是单体？
    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), x = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = in.nextInt();

        Arrays.sort(arr);
        int xNum = 0;
        int i = 0;
        for (; i < n; i++) {
            if (x >= n - i) break;
            while (xNum < arr[i]) xNum++;
        }

        long sum = x * (long)xNum;
        while (i < n) {
            sum += arr[i++] - xNum;
        }
        System.out.println(sum);
    }



    // BC138 矩阵转置
    public static void main4(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                arr[i][j] = in.nextInt();
        }

        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }



    // 42. 接雨水
    public int trap(int[] height) {
        Deque<Integer> stack = new ArrayDeque<>();
        int res = 0, n = height.length;

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int index = stack.pop();
                if (stack.isEmpty()) break;
                int w = i - stack.peek() - 1;
                int h = Math.min(height[i], height[stack.peek()]) - height[index];
                res += w * h;
            }
            stack.push(i);
        }
        return res;
    }



    // kotori和n皇后
    public static void main5(String[] args) {
        Scanner in = new Scanner(System.in);
        int k = in.nextInt();
        // 1. 创建辅助数组并统计
        Set<Integer> rows = new HashSet<>(), cols = new HashSet<>();
        Set<Integer> tmp1 = new HashSet<>(), tmp2 = new HashSet<>();

        boolean[] isConflict = new boolean[k + 1];
        int flag = -1;
        for (int i = 0; i < k; i++) {
            int x = in.nextInt(), y = in.nextInt();
            if (flag != -1) continue;

            if (cols.contains(x) || rows.contains(y) || tmp1.contains(y - x) || tmp2.contains(x + y)) {
                flag = i + 1;
            }
            cols.add(x);
            rows.add(y);
            tmp1.add(y - x);
            tmp2.add(x + y);

        }

        // 2. 返回查询结果
        int t = in.nextInt();
        while (t-- > 0) {
            int i = in.nextInt();
            if (flag != -1 && i >= flag) System.out.println("Yes");
            else System.out.println("No");
        }

    }



    // NC393 取金币
    public int getCoins (ArrayList<Integer> coins) {
        // dp[i][j]:区间 i ~ j 的金币全部拿走，能获得的最大积分是多少
        int n = coins.size();
        int[] arr = new int[n + 2];
        for (int i = 1; i <= n; i++) arr[i] = coins.get(i - 1);
        arr[0] = arr[n + 1] = 1;

        int[][] dp = new int[n + 2][n + 2];
        for (int i = n; i >= 1; i--) {
            for (int j = i; j <= n; j++) {
                for (int k = i; k <= j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + arr[k] * arr[i - 1] * arr[j + 1]);
                }
            }
        }
        return dp[1][n];
    }




    // 四个选项
    private static int[] na_d;
    private static List<Integer>[] arr;        // 统计每一题应该与哪些题答案相同
    private static int[] records;    // 记录每一题的答案是什么
    private static int res;
    public static void main6(String[] args) {
        Scanner in = new Scanner(System.in);
        na_d = new int[5];
        for (int i = 1; i <= 4; i++) {
            na_d[i] = in.nextInt();
        }
        int m = in.nextInt();
        arr = new List[13];
        records = new int[13];
        Arrays.setAll(arr, i -> new ArrayList<Integer>());

        for (int i = 0; i < m; i++) {
            int a = in.nextInt(), b = in.nextInt();
            arr[a].add(b);
            arr[b].add(a);
        }
        for (int i = 1; i <= 12; i++) {
            for (int j = 0; j < arr[i].size(); j++) {
                for (int x : arr[arr[i].get(j)]) {
                    if(!arr[i].contains(x)) arr[i].add(x);
                }
            }
        }

        dfs(1);
        System.out.println(res);
    }
    private static void dfs(int pos) {
        if (pos == 13) {
            res++;
            return;
        }
        // 记录是否需要和哪道题答案一致
        int flag = 0;
        for (int j = 1; j < pos; j++) {
            if (arr[pos].contains(j)) {
                flag = records[j];
                break;
            }
        }

        for (int i = 1; i <= 4; i++) {
            if (na_d[i] <= 0) continue;
            if (flag > 0 && i != flag) continue;
            records[pos] = i;
            na_d[i]--;
            dfs(pos + 1);
            na_d[i]++;
        }
    }




    // 疯狂的自我检索者
    public static void main7(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int sum = 0;
        for (int i = 0; i < n - m; i++) {
            sum += in.nextInt();
        }

        System.out.println((sum + m) * 1.0 / n);
        System.out.println((sum + m * 5) * 1.0 / n);
    }



    // NC115 栈和排序
    public int[] solve (int[] a) {
        int n = a.length;
        boolean[] isPush = new boolean[n + 1];
        int[] res = new int[n];
        int k = 0;

        int flag = n;   // 期望加入结果集的值
        Deque<Integer> stack = new ArrayDeque<>();
        for (int x : a) {
            stack.push(x);
            isPush[x] = true;

            // 先更新 下一次期望要出栈的数
            while (isPush[flag]) flag--;

            while (!stack.isEmpty() && stack.peek() > flag) {
                res[k++] = stack.pop();
            }
        }
        return res;
    }




    // 加减
    public static void main8(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long k = in.nextLong();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = in.nextInt();

        // 1. 排序
        Arrays.sort(arr);
        // 2. 统计前缀和
        long[] prevSum = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            prevSum[i] = prevSum[i - 1] + arr[i - 1];
        }
        // 3. 枚举区间（滑动窗口优化）
        int left = 0, right = 0;
        int res = 0;
        while (right < n) {
            while (calCost(left, right, arr, prevSum) > k) {
                left++;
            }
            res = Math.max(res, right - left + 1);
            right++;
        }

        System.out.println(res);
    }
    private static long calCost(int left, int right, int[] arr, long[] prevSum) {
        int mid = (left + right) / 2;
        return (long) (mid - left) * arr[mid] - (prevSum[mid] - prevSum[left])
                + (prevSum[right + 1] - prevSum[mid + 1]) - (long) (right - mid) * arr[mid];
    }



    // 260. 只出现一次的数字 III
    public int[] singleNumber(int[] nums) {
        int n = nums.length;
        int num = 0;
        for (int x : nums) num ^= x;
        // 1. 寻找这两个数之间二进制位，第一次不同的位置
        int flag = 0;
        while (flag < 32) {
            if ((num>>flag & 1) == 1) break;
            flag++;
        }
        // 2. 将二进制位中第 flag 位为 1 的数归为一组
        int tmp = 0;
        for (int x : nums) {
            if ((x>>flag & 1) == 1) tmp ^= x;
        }
        // 3. tmp 为其中的一个数
        return new int[]{tmp, num ^ tmp};
    }


    // 46. 全排列
    //private List<List<Integer>> res;
    //    private List<Integer> path;
    //    private boolean[] vis;
    //
    //    public List<List<Integer>> permute(int[] nums) {
    //        int n = nums.length;
    //        res = new ArrayList<>();
    //        path = new ArrayList<>();
    //        vis = new boolean[n];
    //
    //        dfs(0, nums);
    //        return res;
    //    }
    //    private void dfs(int pos, int[] nums) {
    //        if (pos == nums.length) {
    //            res.add(new ArrayList<>(path));
    //            return;
    //        }
    //
    //        for (int i = 0, n = nums.length; i < n; i++) {
    //            if (vis[i]) continue;
    //            path.add(nums[i]);
    //            vis[i] = true;
    //            dfs(pos + 1, nums);
    //            path.remove(path.size() - 1);
    //            vis[i] = false;
    //        }
    //    }



    // LCR 084. 全排列 II
    // private List<List<Integer>> res;
    //    private List<Integer> path;
    //    private boolean[] vis;
    //
    //    public List<List<Integer>> permuteUnique(int[] nums) {
    //        int n = nums.length;
    //        res = new ArrayList<>();
    //        path = new ArrayList<>();
    //        vis = new boolean[n];
    //
    //        Arrays.sort(nums);
    //        dfs(nums);
    //        return res;
    //    }
    //
    //    private void dfs(int[] nums) {
    //        if (path.size() == nums.length) {
    //            res.add(new ArrayList<>(path));
    //            return;
    //        }
    //
    //        for (int i = 0, n = nums.length; i < n; i++) {
    //            if (!vis[i] && (i == 0 || (nums[i] != nums[i - 1] || vis[i - 1]))) {
    //                path.add(nums[i]);
    //                vis[i] = true;
    //                dfs(nums);
    //                path.remove(path.size() - 1);
    //                vis[i] = false;
    //            }
    //        }
    //    }




    // 1765. 地图中的最高点
    public int[][] highestPeak(int[][] isWater) {
        int n = isWater.length, m = isWater[0].length;
        int[] dx = {0,0,1,-1}, dy = {1,-1,0,0};

        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (isWater[i][j] == 1) {
                    q.offer(new int[]{i, j});
                    isWater[i][j] = 0;
                } else isWater[i][j] = -1;
            }
        }

        while (!q.isEmpty()) {
            for (int sz = q.size(); sz > 0; sz--) {
                int[] arr = q.poll();
                int i = arr[0], j = arr[1];
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < n && y >= 0 && y < m && isWater[x][y] == -1) {
                        q.offer(new int[]{x, y});
                        isWater[x][y] = isWater[i][j] + 1;
                    }
                }
            }
        }
        return isWater;
    }



    // 931. 下降路径最小和
    public static int minFallingPathSum(int[][] matrix) throws RuntimeException{
        int n = matrix.length, m = matrix[0].length;
        int[][] dp = new int[n + 1][m + 2];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = dp[i][m + 1] = 0x3f3f3f3f;
        }

        for (int i = 1;  i<= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
            }
        }

        int res = 0x3f3f3f3f;
        for (int j = 1; j <= m; j++) res = Math.min(res, dp[n][j]);
        return res;
    }



    // 137. 只出现一次的数字 II
    public int singleNumber2(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int x : nums) {
                sum += (x>>i) & 1;
            }
            if (sum % 3 == 1) res += 1<<i;
        }
        return res;
    }


    // 1567. 乘积为正数的最长子数组长度
    public int getMaxLen(int[] nums) {
        // f[i]: 以 i 位置为结尾的所有子数组中 乘积为正数的最长子数组的长度
        // g[i]: 以 i 位置为结尾的所有子数组中 乘积为负数的最长子数组的长度
        int n = nums.length;
        int[] f = new int[n + 1], g = new int[n + 1];

        int ret = 0;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            if (x > 0) {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            } else if (x < 0) {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }



    // 152. 乘积最大子数组
    public int maxProduct(int[] nums) {
        // f[i]: 以 i 位置为结尾的所有子数组中，乘积为正数的最大值
        // g[i]: 以 i 位置为结尾的所有子数组中，乘积为负数的最小值
        int n = nums.length;
        if (n == 1) return nums[0];
        int[] f = new int[n + 1], g = new int[n + 1];

        int res = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            if (x > 0) {
                f[i] = Math.max(x, f[i - 1] * x);
                g[i] = g[i - 1] * x;
            } else if (x < 0) {
                f[i] = g[i - 1] * x;
                g[i] = Math.min(x, f[i - 1] * x);
            }
            res = Math.max(res, f[i]);
        }
        return res;
    }



    // 413. 等差数列划分
    public int numberOfArithmeticSlices(int[] nums) {
        // dp[i]: 以 i 位置为结尾的所有子数组中等差子数组的个数
        int n = nums.length;
        int[] dp = new int[n];

        int res = 0;
        for (int i = 2; i < n; i++) {
            int x = nums[i - 2], y = nums[i - 1], z = nums[i];
            if (z - y == y - x) dp[i] = dp[i - 1] + 1;
            res += dp[i];
        }
        return res;
    }



    // 467. 环绕字符串中唯一的子字符串
    public int findSubstringInWraproundString(String ss) {
        // dp[i]: 以 i 位置为结尾的所有子串中字典序连续的子串的个数
        int n = ss.length();
        char[] s = ss.toCharArray();
        int[] dp = new int[n];
        // dp[i]: 字符串s中，以 a ~ z 中某个字母为结尾且字典序连续的子串的个数
        int[] hash = new int[26];
        dp[0] = 1;
        hash[s[0] - 'a'] = 1;

        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            char ch1 = s[i - 1], ch2 = s[i];
            if (ch1 + 1 == ch2 || (ch2 == 'a' && ch1 == 'z')) {
                dp[i] += dp[i - 1];
            }
            hash[ch2 - 'a'] = Math.max(dp[i], hash[ch2 - 'a']);
        }

        int res = 0;
        for (int count : hash) res += count;
        return res;
    }



    // 140. 单词拆分 II
    public List<String> wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        s = " " + s;
        // dp[i]:若第 0 ~ i 个字母能够构成句子，增加单词间的空格，存放所有合法的句子
        List<String>[] dp = new List[n + 1];
        Arrays.setAll(dp, i -> new ArrayList<>());
        dp[0].add("");
        // 统计词典中出现的单词
        Set<String> hash = new HashSet<>();
        for (String word : wordDict) hash.add(word);

        for (int i = 1; i <= n; i++) {
            for (int j = i; j >= 1; j--) {
                String tmp = s.substring(j, i + 1);
                if (hash.contains(tmp) && (dp[j - 1].size() > 0)) {
                    for (String str : dp[j - 1]) {
                        StringBuilder stb = new StringBuilder(str);
                        if (stb.length() > 0) stb.append(' ');
                        stb.append(tmp);
                        dp[i].add(stb.toString());
                    }
                }
            }
        }
        return dp[n];
    }



    // 227. 基本计算器 II
    public int calculate(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        char[] arr = s.toCharArray();
        char op = '+';
        for (int i = 0, n = arr.length; i < n; ) {
            char ch = arr[i];
            if (ch == ' ') i++;
            else if (ch >= '0' && ch <= '9') {
                // 提取数字
                int num = 0;
                while (i < n && arr[i] >= '0' && arr[i] <= '9') {
                    num = num * 10 + arr[i++] - '0';
                }
                // 与前一个运算符进行计算
                if (op == '-') num = -num;
                else if (op == '*') num *= stack.pop();
                else if (op == '/') num = stack.pop() / num;
                stack.push(num);
            } else {
                op = arr[i++];
            }
        }

        int res = 0;
        while (!stack.isEmpty()) res += stack.pop();
        return res;
    }



    // 692. 前K个高频单词
    public List<String> topKFrequent(String[] words, int k) {
        // 1. 统计每个单词出现的次数
        Map<String,Integer> hash = new HashMap<>();
        for (String s : words) {
            hash.put(s, hash.getOrDefault(s, 0) + 1);
        }
        // 2. 将各个单词入堆
        // 小根堆
        PriorityQueue<Pair<String,Integer>> pq = new PriorityQueue<>((a, b) -> {
            if (!Objects.equals(a.getValue(), b.getValue())) {
                return a.getValue() - b.getValue();
            }
            return b.getKey().compareTo(a.getKey());
        });
        for (Map.Entry<String,Integer> e : hash.entrySet()) {
            pq.offer(new Pair(e.getKey(), e.getValue()));
            if (pq.size() > k) pq.poll();
        }
        // 3. 返回结果
        List<String> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            res.add(pq.poll().getKey());
        }
        Collections.reverse(res);
        return res;
    }



    // LCR 114. 火星词典
    public String alienOrder(String[] words) {
        // 1. 统计所有出现过的字母
        boolean[] vis = new boolean[26];
        for (String s : words) {
            for (char ch : s.toCharArray()) {
                vis[ch - 'a'] = true;
            }
        }

        // 2. 遍历 words，根据字母的字典序统计入度和出度
        List<Character>[] outs = new List[26];
        Arrays.setAll(outs, i -> new ArrayList<>());
        int[] ins = new int[26];
        int n = words.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int cur = 0;
                int len1 = words[i].length(), len2 = words[j].length();
                while (cur < len1 && cur < len2 && words[i].charAt(cur) == words[j].charAt(cur)) {
                    cur++;
                }
                // 出现不符合常识的情况
                if (cur < len1 && cur == len2) return "";
                if (cur == len1) continue;

                char ch1 = words[i].charAt(cur), ch2 = words[j].charAt(cur);
                if (!outs[ch1 - 'a'].contains(ch2)) {
                    outs[ch1 - 'a'].add(ch2);
                    ins[ch2 - 'a']++;
                    break;
                }

            }
        }
        // 3. 将入度为 0 且在词典出现过的字母入队
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < 26; i++) {
            if (ins[i] == 0 && vis[i]) q.offer(i);
        }
        // 4. 尝试拓扑排序
        StringBuilder res = new StringBuilder();
        while (!q.isEmpty()) {
            for (int sz = q.size(); sz-- > 0; ) {
                int index = q.poll();
                res.append((char)(index + 'a'));
                for (char ch : outs[index]) {
                    if (--ins[ch - 'a'] == 0) q.offer(ch - 'a');
                }
            }
        }

        for (int x : ins) {
            if (x > 0) return "";
        }
        return res.toString();
    }



    // 455. 分发饼干
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0, j = 0;
        int res = 0;

        for (; i < g.length && j < s.length; j++) {
            if (s[j] >= g[i]) {
                i++;
                res++;
            }
        }
        return res;
    }



    // 45. 跳跃游戏 II
    public int jump(int[] nums) {
        int cur = 0, last = 0, n = nums.length;
        if (n == 1) return 0;
        int step = 0;

        while (cur <= last) {
            int nextLast = last;
            while (cur <= last) {
                if (cur + nums[cur] >= n - 1) return step + 1;
                else nextLast = Math.max(nextLast, cur + nums[cur]);
                cur++;
            }
            step++;
            last = nextLast;
        }
        return -1;
    }



    // 2418. 按身高排序
    public String[] sortPeople(String[] names, int[] heights) {
        int n = names.length;
        Integer[] indexs = new Integer[n];
        for (int i = 0; i < n; i++) indexs[i] = i;
        Arrays.sort(indexs, (a, b) -> heights[b] - heights[a]);

        String[] res = new String[n];
        for (int i = 0; i < n; i++) res[i] = names[indexs[i]];
        return res;
    }



    // LCP 30. 魔塔游戏
    public int magicTower(int[] nums) {
        int sum = 1;
        for (int x : nums) sum += x;
        if (sum <= 0) return -1;

        int res = 0, i = 0, n = nums.length;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (sum = 1; i < n; i++) {
            if (nums[i] < 0) minHeap.offer(nums[i]);
            sum += nums[i];
            if (sum <= 0) {
                sum -= minHeap.poll();
                res++;
            }
        }
        return res;
    }
}
